import java.util.ArrayList;
import java.util.Vector;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class BinaryTreeLevelOrderTraversal {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return res;
		Vector<TreeNode> vec = new Vector<TreeNode>();
		int head = 0, rear = -1;
		vec.add(root);
		rear = vec.size();
		ArrayList<Integer> list;
		while (head < vec.size()) {
			list = new ArrayList<Integer>();
			while (head < rear) {
				root = vec.get(head++);
				list.add(root.val);
				if (root.left != null)
					vec.add(root.left);
				if (root.right != null)
					vec.add(root.right);
			}
			res.add(list);
			rear = vec.size();
		}
		return res;
	}

	public static void main(String[] args) {

	}

}
